package cn.bellychang.PriorityLinkedList.wangwenjun;

import java.util.NoSuchElementException;
import java.util.Objects;

/**
 * @author: bellychang
 * @date: 2020/2/4
 */
public class BellyPriorityLinkedList<E extends Comparable> {

    private static final String PLAIN_NULL = "null";
    private Node<E> head;

    private final Node<E> NULL = null;

    private BellyPriorityLinkedList() {
        this.head = NULL;
    }

    private int size;

    public int size() {
        return this.size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean contains(E element) {
        Node<E> temp = head;
        while (Objects.nonNull(temp)) {
            if (temp.value == element) {
                return true;
            }
            temp = temp.next;
        }
        return false;
    }

    public static <E extends Comparable> BellyPriorityLinkedList<E> of(E... elements) {
        BellyPriorityLinkedList list = new BellyPriorityLinkedList();
        if (Objects.nonNull(elements)) {
            for (E element : elements) {
                list.addFirst(element);
            }
        }
        return list;
    }

    public void addFirst(E element) {
        Node<E> newNode = new Node<>(element);
        // add first
        if (head == NULL || element.compareTo(head.getValue()) > 0) {
            newNode.next = head;
            head = newNode;
        } else {
            // add intermediate
            // traverse the linked list to find the right position
            Node<E> temp = findRightPosition(element);
            if (Objects.nonNull(temp)) {
                newNode.next = temp.next;
            }
            temp.next = newNode;
        }
        size++;
    }

    /**
     * should insert between temp and temp.next
     *
     * @param element
     * @return
     */
    private Node<E> findRightPosition(E element) {
        Node<E> temp = head;
        while (Objects.nonNull(temp)) {
            if (Objects.nonNull(temp.next)) {
                if (element.compareTo(temp.getValue()) < 0 && element.compareTo(temp.next.getValue()) >= 0) {
                    return temp;
                }
                temp = temp.next;
            } else {
                return temp;
            }
        }
        return head;
    }

    @Override
    public String toString() {
        if (this.isEmpty()) {
            return PLAIN_NULL;
        }
        StringBuilder builder = new StringBuilder();
        Node<E> temp = head;
        while (Objects.nonNull(temp)) {
            builder.append(temp.toString()).append("->");
            temp = temp.next;
        }
        String result = builder.toString();
        return result.substring(0, result.length() - 2);
    }


    public E removeFirst() {
        if (this.isEmpty()) {
            throw new NoSuchElementException("this linked list is empty");
        }
        Node<E> temp = head;
        head = head.next;
        size--;
        return temp.getValue();
    }

    static class Node<E> {
        private E value;

        private Node<E> next;

        public Node(E value) {
            this.value = value;
        }

        public E getValue() {
            return value;
        }

        @Override
        public String toString() {
            return value.toString();
        }
    }
}
